LRU缓存的功能

LRU缓存具有两种功能：

  • get(key)：获取key对应的value，不存在返回-1
  • set(key, value)：设置<key, value>
    • 缓存已满，删除最近最久未被使用的节点，添加新节点进缓存
    • 缓存未满：
      • 节点存在，修改value
      • 节点不存在，添加新节点进缓存

解题思路

由于LRU缓存插入和删除操作频繁，使用双向链表维护缓存节点。

  • 新节点：凡是被访问（新建、修改命中、访问命中）过的节点，一律在访问完成后移动到双向链表尾部，保证尾部始终为最新节点
  • 旧节点：保证链表头部始终为最旧节点，LRU缓存策略删除时表现为删除双向链表头部

由于链表不支持随机访问，使用HashMap+双向链表实现LRU缓存：

  • HashMap中键值对：<key, CacheNode>
  • 双向链表：维护缓存节点CacheNode

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
class Solution {
  private HashMap<Integer, CacheNode> map;
  private int capacity;
  private CacheNode head = new CacheNode(-1, -1);
  private CacheNode tail = new CacheNode(-1, -1);
  
  private class CacheNode {
    int key, value;
    CacheNode pre, next;
    CacheNode(int key, int value) {
      this.key = key;
      this.value = value;
      this.pre = null;
      this.next = null;
    }
    
    public Solution(int capacity) {
      this.capacity = capacity;
      this.map = new HashMap<>();
    }
    
    private void moveToTail(CacheNode target, boolean isNew) {
      if (target != tail.next) {
        if (!isNew) {
          target.pre.next = target.next;
          target.next.pre = target.pre;
        }
        tail.next.next = target;
        target.pre = tail.next;
        tail.next = target;
      }
    }
    
    public int get(int key) {
        if (map.containsKey(key)) {
            CacheNode target = map.get(key);
            // 将已有节点移动到链表尾部
            moveToTail(target, false);
            // 此时链表尾部tail.next = target，更新next指向null，防止出现环
            tail.next.next = null;
            return target.value;
        }
        return -1;
    }
    
    public void set(int key, int value) {
      if (map.containsKey(key)) {
        CacheNode target = map.get(key);
        target.value = value;
        map.put(key, target);
        moveToTail(target, false);
      } else if (map.size() < capacity) {
        CacheNode newNode = new CacheNode(key, value);
        map.put(key, newNode);
        if (head.next == null) {
          head.next = newNode;
          newNode.pre = head;
          tail.next = newNode;
        } else {
          moveToTail(newNode, true);
        }
      } else {
        CacheNode newNode = new CacheNode(key, value);
        map.remove(head.next.key);
        map.put(key, newNode);
        if (head.next == tail.next) {
          head.next = newNode;
          tail.next = newNode;
        } else {
          head.next.next.pre = head;
          head.next = head.next.next;
          moveToTail(newNode, true);
        }
      }
    }
  }
}

说明

本文转自剑指offer/LeetCode146/LintCode134_LRU缓存实现。